package com.origin.niuke.greedy;

/**
 * NC235 加油站
 * 算法：贪心
 * 求出每一趟剩余的油量，并累加，记录剩余的油量
 * 如果某一趟的剩余油量为负数，则将下一个加油站作为起始点
 *
 * @author yezh
 * @date 2022/12/14 20:31
 */
public class NC235 {

    public int gasStation(int[] gas, int[] cost) {
        // write code here
        int n = gas.length, ans = 0, ret = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            ret += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (ret < 0) {
                ans = (i + 1) % n;
                ret = 0;
            }
        }
        return sum >= 0 ? ans : -1;
    }

}
